package algorithm;

public class leetcode_0581 {
    public int findUnsortedSubarray(int[] nums) {
        int len=nums.length;
        int left=len-1;
        int right=0;
        int[] stack=new int[len];
        int current=1;
        stack[0]=nums[0];
        for(int i=1;i<len;++i){
            if(stack[current-1]<=nums[i]){
                stack[current]=nums[i];
                current++;
            }
            else{
                while(current>0&&nums[i]<stack[current-1]){
                    current--;
                }
                left=Math.min(left,current);
                stack[current]=nums[i];
                current++;
            }
        }
        current=1;
        stack[0]=nums[len-1];
        for(int i=len-2;i>=0;--i){
            if(stack[current-1]>=nums[i]){
                stack[current]=nums[i];
                current++;
            }
            else {
                while(current>0&&nums[i]>stack[current-1]){
                    current--;
                }
                right=Math.max(right,len-1-current);
                stack[current]=nums[i];
                current++;
            }
        }
        if(left>=right) return 0;
        return right-left+1;
    }
}
